This invention relates generally to the field of digital data processing apparatus and more specifically to a digit-reversal computer and method useful in performing fast discrete transforms on input data.
Transforms, such as the Fourier transform, have been well known to mathematicians, scientists, engineers and others for many years. These transforms are tools used in many fields such as medicine, economics, and engineering to analyze data. For example, when the input data represents time-varying electrical signals, the Fourier transform is often performed to identify the frequency components within the electrical signals. Similarly, an inverse Fourier transform is often performed to produce a time-varying electrical signal from frequency components. At times, data may be processed by first performing the Fourier transform, modifying the frequency components in a desired way, and inverting the transform.
For general background information relating to transforms, reference is made to the book "The Fourier Transform and its Applications" McGraw-Hill, Inc., 2nd Ed. 1978 by Ronald N. Bracewell.
In digital data processing apparatus, the Fourier transform is normally performed with discrete values of input data in accordance with the well-known discrete Fourier transform (DFT). The number N of values of input data may vary, but the larger the value of N the greater the resolution of the output data. In order to practically and efficiently perform N-length DFT's, digital computers are utilized. Even using digital computers, however, performance of N-length DFT's for large N is still a formidable task. For this reason, many prior art techniques have been developed to more efficiently perform the N-length discrete Fourier transform.
One significant technique for improving the efficiency of performing the discrete Fourier transform is described in the article by J. W. Cooley and J. W. Tukey, "An Algorithm for the Machine Calculation of Complex Fourier Series", Math of Computation, Vol. 19, pp. 297-301, April 1965. When the Cooley-Tukey algorithm was utilized on a general purpose computer, a more than fifty times improvement in processing time occurred for 1024-point DFT. The algorithm became known as the Cooley-Tukey fast Fourier transform (FFT). Many other Fourier transform algorithms such as the Sande-Tukey FFT have been proposed for more efficiently performing the N-length DFT.
In addition to Fourier transforms, other transforms have proved to be useful. For example, the Discrete Bracewell Transform (DBT) sometimes called the Discrete Hartley Transform (DHT) had led to the Fast Bracewell (Hartley) Transform, FBT or FHT, described in the above-identified cross-referenced application and in the article by R. N. Bracewell, "The Fast Hartley Transform," Proc. IEEE, vol. 72, pp. 1010-1018, August 1984.
The FFT, FBT (FHT) "fast" transforms are typically radix-2 transforms but more generally may be radix-B transforms where B is any positive integer greater than 1. Radix-B transforms rely on the property that a full N-length transform can be easily constructed from B transforms of length N/B. These fast transforms achieve speed by reiteratively decomposing the N-length transform into many elementary smaller transforms until it consists of transforms which are usually 1-length transforms. In many applications, these transforms are executed "in-place" so as to economize on the quantity of memory space used. For "in-place" execution, the same memory location (or "place") is used for data input, for data output, and for intermediate data computations. In such "in-place" FFT or FHT computers, the reordering required to counteract the effect of the transform decompositions is achieved by a particular permutation of the elements of the data sequence, which is described as follows.
In the radix-B fast transforms performed "in-place", an initial array represented as a sequence of elements X(i) indexed by i, where i ranges from 0 to N-1, is permuted to form a reordered array represented as a sequence of elements X(j) indexed by j where j ranges from 0 to N-1. The transform is achieved when certain of the elements X(i) having index i are swapped resulting in the elements X(j) having index j. The transform (permutation, conversion, reordering) is called digit-reversing, because if i is the index represented as a string of digits, base B, then j is that index having a representation that is the same string of digits written in reverse order, where N is a power of B and B is greater than or equal to 2.
The transform is a fast radix-B transform of N elements where B is greater than or equal to 2 and where N equals B.sup.P for some integral power P. Under these conditions, the permutation required for a fast transform is the "digit-reversing" permutation implemented when certain elements of X(i) are swapped resulting in X(j) where j is the "digit-reversing" of i (and vice versa). The digit-reverse of i can be found by writing i as a base-B number with P digits, adding zeroes to the front of the representation of i in base B if necessary, and reversing the order of the digits of i to obtain j. Since the highest index, N-1, is B.sup.P -1, all of the indices can be written in P base-B digits. Thus i can be written as a string of digits as follows: EQU i=(b.sub.P b.sub.P-1. . . b.sub.k. . . b.sub.2 b.sub.1).sub.B Eq.(A)
where the b.sub.k are base-B digits and k has values P, P-1, . . . , 2, 1. Then j, the digit-reverse of i, is the base B number obtained by writing the string of numbers of i in reverse as follows: EQU j=(b.sub.1 b.sub.2. . . b.sub.k. . . b.sub.P-1 b.sub.P).sub.B. Eq.(B)
where the b.sub.k are base-B digits and k has values 1, 2, . . . , k, P-1, P.
An example of the digit reversal of i and j for base B=2 of Eq.(A) and Eq.(B) is shown in the following TABLE A. Note that since N=8 and B=2 in the TABLE A example, P=3 and so the base 2 representations of i and j have P=3 digits. For example, for i.sub.10 equal to 3, i.sub.2 equals (011).sub.2 where b.sub.3 =0, b.sub.2 =1 and b=1. The digit reverse of i.sub.10 equal to 3.sub.10 corresponding to i.sub.2 equal (011).sub.2 is j.sub.2 equal to (110).sub.2 where b.sub.1 =1, b.sub.2 =1, and b.sub.3 =0 and corresponding to j.sub.10 equal to b.sub.10. For each of the eight values of i.sub.2 and j.sub.2 in TABLE A, j.sub.2 =(b.sub.1 b.sub.2 b.sub.3) and j.sub.2 is the digit reverse of i.sub.2 =(b.sub.3 b.sub.2 b.sub.1).
TABLE A ______________________________________ i.sub.10 i.sub.2 j.sub.10 j.sub.2 ______________________________________ 0 000 0 000 1 001 4 100 2 010 2 010 3 011 6 110 4 100 1 001 5 101 5 101 6 110 3 011 7 111 7 111 ______________________________________
In TABLE A, the columns i.sub.10 and j.sub.10 depict the i and j indicies in base-10 numbers while the columns i.sub.2 and j.sub.2 depict the indicies in corresponding base-2 numbers.
One example of the "in-place" permutation for a fast transform appears in the above-identified cross-referenced Bracewell application. In that application, the Discrete Bracewell Transform is arrived at by means of a Fast Bracewell Transform (FBT) which proceeds using a plurality of stages. The first stage ("zero" stage) receives an input sequence of N input data values, F.sub.0,K, which are given for index values of k from 0 to N-1 as follows: EQU F.sub.0,K =F.sub.0,0, . . . , F.sub.0,k, . . . , F.sub.0,(N-1).
The first stage of the FBT transform permutes the order of the input sequence using a bisecting permutation (or bit-reversing permutation), that is, a digit reversing permutation in which B=2. The bisecting permutation is carried out by sorting the original sequence of elements into odd-numbered and even-numbered elements thereby bisecting the original sequence into two segments, an odd segment and an even segment. The elements are then reordered with the odd-segment first followed by the even-segment. The new sequence in turn, has each segment odd-even bisected and reordered to form a new sequence. The odd-even bisecting and reordering is performed P-1 times for N-length data when N equals 2.sup.P. The bisecting permutation thus performed results in a sequence of N permuted data values, F.sub.1,K, which are given for values of k from 0 to N-1 as follows: EQU F.sub.1,K =F.sub.1,0, . . . , F.sub.1,k, . . . , F.sub.1,(N-1).
The permutation operation described functions to receive the N data values F.sub.0,K and reorder them as the N data values F.sub.1,K. The sequence of the index k for the data values F.sub.0,K is denominated as i so that the elements F.sub.0,k correspond to the elements X(i). The reordered sequence of the index k for the data values F.sub.1,K is denominated j where j is the base-2 digit reversal of i as explained with reference to Eq.(A) and Eq.(B) so that the elements F.sub.1,k corresponding to the elements X(j).
An N equal to 16 example of the digit reversal permutation appears in the following TABLE B where the indicies of F are shown as base-10 numbers:
TABLE B ______________________________________ k=i k=j F.sub.1,k F.sub.0,k ______________________________________ F.sub.1,0 = F.sub.0,0 F.sub.1,1 = F.sub.0,8 F.sub.1,2 = F.sub.0,4 F.sub.1,3 = F.sub.0,12 F.sub.1,4 = F.sub.0,2 F.sub.1,5 = F.sub.0,10 F.sub.1,6 = F.sub.0,6 F.sub.1,7 = F.sub.0,14 F.sub.1,8 = F.sub.0,1 F.sub.1,9 = F.sub.0,9 F.sub.1,10 = F.sub.0,5 F.sub.1,11 = F.sub.0,13 F.sub.1,12 = F.sub.0,3 F.sub.1,13 = F.sub.0,11 F.sub.1,14 = F.sub.0,7 F.sub.1,15 = F.sub.0,15 ______________________________________
Other FFT permutation algorithms are described by E. O. Brigham, "The Fast Fourier Transform", Englewood Cliffs, N.J., Prentice-Hall, 1974, Chap. 10, 11, pp. 148-197. Brigham considers all of the indices i, except the first and last, digit-reversing them, and if j is greater than i, then the array elements are interchanged. In, for example, the B=2 case, the bit-reversing is done by peeling each bit (a "bit" is a binary digit) off one end of the binary representation of i and reassembling the bits in the reverse order to form the binary representation of j. This method has complexity of order O(N log.sub.2 N). More advanced permutation algorithms take advantage of some of the regularity in the i versus j relationship to form the bit-reversed indices by a small series of additions of powers of two. At least one and as many as log.sub.2 N additions are required to calculate each j. Also, such algorithms still digit-reverse all of the indices i from 0 to N-1, and only make a change to the F array if j is greater than i. Since j is greater than i for only a little fewer than N/2 of the N values of i, calculating j for all i is clearly a major source of inefficiency in this method.
The efficiency of permutation algorithms is measured in terms of both execution times and number of arithmetic operations. The fastest algorithm known apart from the present invention, is implemented in the Pascal procedure shown in the following TABLE C. Note that "powersof2" is an array containing the powers of 2, for example, powersof2[1]=2, powersof2[2]=4.
TABLE C ______________________________________ begin j := -1; for i := 0 to N-3 do begin powersof2index := P; repeat powersof2index := powersof2index - 1: j := j - powersof2 [powersof2index] 1;until j &lt; j := j + powersof2 [powersof2index]; if j &gt; 1 then Swap(i + 1, j + 1) end { for } end; ______________________________________
TABLE C is the B=2 bit-reversing Buneman algorithm found in the paper by O. Buneman, "Two Hartley Transforms for the Price of One FFT" submitted for publication to the SIAM Journal on Scientific and Statistical Computing.
While various permutation techniques such as those described above have been known, there is a need for improved and more efficient computers and methods for performing permutations for use in fast transforms.